package leetcode.editor.cn.q1_300.q;

import java.util.Stack;

/**
 * @author qidi
 * @date 2021-11-09 16:27:48
 */
class Q0032_LongestValidParentheses {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestValidParentheses(String s) {
            if (s.length() == 0 || s.length() == 1) return 0;

            int max = 0;
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.add(i);
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.add(i);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }

            return max;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0032_LongestValidParentheses().new Solution();
//        System.out.println(solution.longestValidParentheses(")()())"));
//        System.out.println(solution.longestValidParentheses("())"));
//        System.out.println(solution.longestValidParentheses(")(()())())"));
//        System.out.println(solution.longestValidParentheses("((()()())))"));
//        System.out.println(solution.longestValidParentheses("()(())"));
//        System.out.println(solution.longestValidParentheses("((()))())"));
        System.out.println(solution.longestValidParentheses("()(()"));
        System.out.println(solution.longestValidParentheses("())()"));
        System.out.println(solution.longestValidParentheses(")))"));
    }
}